package com.nan.leetcode;

import java.util.*;

public class Test5 {
    //给定一个非空整数数组，除了某个元素只出现一次以外，
    // 其余每个元素均出现两次。找出那个只出现了一次的元素。
    public int singleNumber(int[] nums) {
        //使用一个Map统计每个数字出现的次数，最后再遍历Map，看谁是值出现一次
        Map<Integer,Integer> map=new HashMap<>();
        //key表示当前数字是谁，value表示该数字出现几次
        for(int x:nums){
            //如果x不存在，就插入新的键值对，value就记为1
            //如果x存在，就在原来的value基础上加一
            Integer value=map.get(x);
            if(value==null){
                map.put(x,1);
            }else{
                map.put(x,value+1);
            }
        }
        //此时map里面就包含了每个数字出现的次数
        //遍历map找出那个只出现一次的数字
        for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            if(entry.getValue().equals(1)){
                return entry.getKey();
            }
        }
        return 0;
    }

    public static void main1(String[] args) {
        int[] nums={1,1,2,2,3};
        Test5 test5=new Test5();
       int ret= test5.singleNumber(nums);
        System.out.println(ret);
    }
    //给你一个长度为 n 的链表，
    // 每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
    //借助Map完成新旧节点之间的关系
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }
    public Node copyRandomList(Node head) {
        //先创建一个Map，key是旧的节点，value是新的节点
        Map<Node,Node> map=new HashMap<>();
        //遍历旧的链表，同时构造出旧节点对应的新节点，插入到Map中
        for(Node cur=head;cur!=null;cur=cur.next){
            map.put(cur,new Node(cur.val));
        }
        //接下来把新链表的next给连接上
        //再次遍历旧链表
        for(Node cur=head;cur!=null;cur=cur.next){
            //取出cur对应的新节点
            map.get(cur).next=map.get(cur.next);
            map.get(cur).random=map.get(cur.random);
        }
        return map.get(head);
    }
    //给你一个字符串 jewels代表石头中宝石的类型，另有一个字符串 stones 代表你拥有的石头。
    // stones中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。
    public int numJewelsInStones(String jewels, String stones) {
        //1.先遍历宝石，把宝石的字符都插入到Set中，2.再遍历自己的石头，
        // 看当前石头是否在宝石的Set中出现，如果出现了就count++即可
        Set<Character> set=new HashSet<>();//Character是char的包装类
        for(int i=0;i<jewels.length();i++){
            set.add(jewels.charAt(i));
        }
        int count=0;
        for(int i=0;i<stones.length();i++){
            if(set.contains(stones.charAt(i))){//如果宝石中包含了石头中的字符
                count++;
            }
        }
        return count;
    }
    //旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。
    // 现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        while(scanner.hasNext()){
            //1.读取两个字符串
            String excepted=scanner.next();//预期要打印的结果
            String actual=scanner.next();//实际要打印的结果
            //大小写忽略，将两个字符串统一转成大写形式
            excepted=excepted.toUpperCase();
            actual=actual.toUpperCase();
            //2.需要找到哪些字符在预期存在，实际不存在
            //借助set，用这个set记录下actual中有哪些字符
            //再遍历excepted，看这里面的哪些字符在Set中不存在
            Set<Character> brokenSet=new HashSet<>();
            Set<Character> actualSet=new HashSet<>();
            for(int i=0;i<actual.length();i++){
                actualSet.add(actual.charAt(i));
            }
            for(int i=0;i<excepted.length();i++) {
                char c = excepted.charAt(i);
                if (actualSet.contains(c)) {//如果实际中包含c,一定不是坏键
                    continue;
                }
                //说明c这个字符对应的键已经是坏了的
                //再使用一个set，记录当前哪些键已经是坏键被输出过了，如果输出过了，就不再输出
                if(brokenSet.contains(c)){
                    continue;
                }
                System.out.print(c);
                brokenSet.add(c);
            }
            System.out.println();
        }
    }
    //给一非空的单词列表，返回前 k 个出现次数最多的单词。
    //返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。
    public List<String> topKFrequent(String[] words, int k) {
        //1.使用map统计words中每个单词出现的次数
        Map<String,Integer> map=new HashMap<>();
        for(String x:words){
            Integer value=map.get(x);
            if(value==0){
                map.put(x,1);
            }else{
                map.put(x,value+1);
            }
        }
        //把所有的key取出来放到list当中
        List<String> wordList=new ArrayList<>(map.keySet());
        //3.把wordList进行排序,需要在sort的第二个参数中传入一个Comparator比较器对象，
        // 用来指定比较规则
        Collections.sort(wordList, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                Integer count1=map.get(o1);//java的匿名内部类能自动捕获到外部的变量
                Integer count2=map.get(o2);
                if(count1.equals(count2)){
                    return o1.compareTo(o2);//出现次数相同，按照字符串的字典序列来
                }
                return count2-count1;
            }
        });
        return wordList.subList(0,k);
    }
}
